Binary tree right side view

Time: O(N); Space: O(H); medium

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

  1           <---
 / \
2   3         <---
 \   \
  5   4       <---

Input: {TreeNode} [1,2,3,None,5,None,4]

Output: [1,3,4]

Example 2:

  1
 / \
2   3

Input: root = {TreeNode} [1,2,3]

Output: [1,3]

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. Recursion

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        self.rightSideViewDFS(root, 1, result)
        return result

    def rightSideViewDFS(self, node, depth, result):
        if not node:
            return

        if depth > len(result):
            result.append(node.val)

        self.rightSideViewDFS(node.right, depth+1, result)
        self.rightSideViewDFS(node.left, depth+1, result)

[3]:

s = Solution1()

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
assert s.rightSideView(root) == [1,3,4]

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
assert s.rightSideView(root) == [1,3]

2. BFS solution

[4]:

class Solution2(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []

        result, current = [], [root]
        while current:
            next_level = []
            for node in current:
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            result.append(node.val)
            current = next_level

        return result

[6]:

s = Solution2()

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
assert s.rightSideView(root) == [1,3,4]

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
assert s.rightSideView(root) == [1,3]